1. Field of the Invention
The present invention relates to RC interconnect and transmission line, and methods to obtain their state space model in time domain and transfer function in frequency domain, and their simulations for their characteristics and evolution, and their practice for various model reduction methods.
2. Description of the Related Art
Over times, VLSI has become larger with more and smaller transistors per square centimeter. With the rapid increase of integration level and speed, IC interconnect becomes one of the important limiting factors of today's VLSI circuit design performance. It has become well accepted that interconnect delay dominates gate delay in current deep submicrometer VLSI circuits. With the continuous scaling of technology and increased die area, especially the chip operation speed increasing, that situation is becoming worse. The average length of the chip interconnect and the chip area occupied by interconnect are both increasing. The advance of high-speed deep-submicron VLSI technology requires chip interconnect and packaging to be modeled by distributed circuits [Reed and Rohrer 1999, Wang et al. 2002]. Such a detailed modeling level eventually results in large scale linear RLC or RC circuits to be analyzed. In transmission line area, it is also well know that the transmission line should be modeled as distributed circuits, resulting in large scale linear RLC or RC circuits.
In circuit design, fast and accurate computer simulation of the behavior of the circuit is important. That is especially true with VLSI, in which hundreds of thousands of circuit elements can be placed on a single chip, and with ULSI, in which millions of circuit elements can be placed on a single chip.
The increasing size of integrated systems creates an explosion in interconnect modeling complexity of unmanageable proportions. As the interconnect complexity gradually increases, its electrical design becomes more challenging. An effort of reducing the circuit order (or size) is then necessary in order to evaluate the circuit performance and characteristics in a reasonable time period, as required by real design practice. The process of reducing linear system order is called linear system order reduction.
In order to design complex circuits properly, accurate characterization of the interconnect behavior and signal transients is required. One interconnect in a VLSI circuit is commonly structured in a single line, a tree and a net. However, a single line is a basic component for a tree and a net. Thus, the process of characterizing signal waveforms in a single line structured interconnect is of primary basis and importance.
There are various model reduction methods, such as Elmore delay model, AWE (Asymptotic Waveform Evaluation) for timing analysis, PVL (Padé approximation via Lanczos approach), Klyrov space decomposition, Klyrov-Arnoldi-based reduced-order modeling, BTM (Balance Truncation Method), and old traditional even length-division order (ELO) modeling.
However, almost all model reduction methods in the state space need to start from an accurate state space high order models of interconnect and transmission line in order to result in a good model reduction, such as Klyrov space method, BTM, ELO, PVL and Arnoldi-based method needs state space system matrix A and input matrix B in state space. On the other hand, model reduction methods in frequency domain via the transfer function need either to start from the above state space model or its accurate transfer function model, such as Elmore model and AWE and ELO.
The original accurate models in state space equation and transfer function are important not only as a basis of an accurate starting point for all various model reduction methods, but also as a basis of performance comparison for checking the approximation of all various model reduction methods.
It is noticed that to get an accurate state space model for the starting point has significantly high computational complexity as shown as follows, in addition to the high computation complexity of model reduction techniques themselves. It is well known that an RC and an RLC interconnect and transmission line can be described as the following differential equation in matrix form based on the KCL or KVL:
                                          Gx            ⁡                          (              t              )                                +                                    C              LC                        ⁢                                          ⅆ                                  x                  ⁡                                      (                    t                    )                                                                              ⅆ                t                                                    =                  bu          ⁡                      (            t            )                                              (        1        )            where G and CLC are parameter matrices related to the parameters of resisters, capacitors and inductors of the interconnect and transmission line and the structure of the line, tree and net, u(t) is the input source vector and x(t) is a vector of the node voltages and inductor currents or the node voltage derivatives. The state space model {A,B,C,D} of an RC interconnect and transmission line is in{dot over (x)}(t)=Ax(t)+Bu(t), y(t)=Cx(t)+Du(t),   (2)where the state variable x(t)εRn, input variable u(t)εR and output variable y(t)εR, and the order n is the number of capacitors in the circuit (a line, tree or net). Thus, it is apparent from equation (1) that the calculation of inverse of matrix CLC and multiplication of CLC−1 with matrix G and vector b are necessary to get matrix A and matrix B in the state space model. From the well known results, the computation complexity of only matrix inverse is O(n2)˜O(n3) depending on the matrix structure and the inverse algorithm, and the computation complexity of n×n matrix multiplication is also O(n3) usually. For very high order system, the matrix inverse calculation leads to calculation singularity problem due to bad condition number of the matrix, making a calculation problem. Note that n should be as large as we can for approaching to a distributed model, and on the other hand, it can be in the order of thousands for a typical large industrial net.
To avoid this difficulty, it is usual to take a suitable small or middle size of order for the original model of distributed RC and RLC interconnect and transmission line by using even length division with its parameters proportional to their length.
It is noticed that the limited number of orders or poles is inappropriate to evaluate the transient response at the nodes of underdamped RLC interconnect and transmission line, which require a much higher order model to accurately capture the transient response. However, highly accurate estimation of signal transients within a VLSI circuit is required for performance-critical modules and nets and to accurately anticipate possible hazards during switching. Also, the increasing performance requirements forces the reduction of the safety margins used in a worst case design, requiring a more accurate delay characterization.
An exact original high order model is much important not only as a starting point for all model reduction methods, but also as an evaluation criterion for all reduced order models. In that an exact original model of a single line interconnect and a transmission line is primary important because it is a basic structure of interconnect and transmission line, but also a basic element to build a tree structure and a net structure of interconnect and transmission lines. However, due to very large size of the original interconnect model, an important and difficult aspect is how to have a method to get its original model in a suitable time and cost-less calculation time. It should be and has to be an exact accurate model of such large order. It not only provides an accurate starting point for model reduction, but also is a basis for checking and evaluating of reduced model performance.
Furthermore, when uncertainties are considered, to investigate robustness of the performance of the VLSI including interconnects needs a through and careful knowledge of interconnects, i.e., its accurate model.
The way to find this distributed linear model usually is from the s-domain by Kirchhoff's law and algebraic equations or from the time domain by Kirchhoff's law and differential equations. However, it is bound to meet calculation of so-high dimension matrix inverse in conventional methods. Due to the distributed interconnect characteristics, the size is very large, e.g., a 106×106 matrix, it is desired to have an elegant closed-form of the state space model and an effective recursive algorithm of the transfer function model for the RC and RLC distributed interconnects and transmission lines to dramatically reduce the calculation complexity. Moreover, simulations based on these models can be developed to capture the transient response in exact or arbitrary accuracy.
It is noticed that there exists some kind of simple algorithms in finding transfer function of interconnect and transmission line. However, it is only an approximation to exact transfer function due to no consideration of load effect or under an assumption of no load effect. One simple example of two-section RC interconnect shows the approximation error. The simple rough method takes a multiplication of each individual section transfer function and leads to a transfer function as
                                                                                          T                  12                                ⁡                                  (                  s                  )                                            =                            ⁢                                                                    1                                          1                      +                                                                        R                          1                                                ⁢                                                  C                          1                                                ⁢                        s                                                                              ·                                      1                                          1                      +                                                                        R                          2                                                ⁢                                                  C                          2                                                ⁢                        s                                                                                            =                                  1                                                                                    R                        1                                            ⁢                                              C                        1                                            ⁢                                              R                        2                                            ⁢                                              C                        2                                            ⁢                                              s                        2                                                              +                                                                  (                                                                                                            R                              1                                                        ⁢                                                          C                              1                                                                                +                                                                                    R                              2                                                        ⁢                                                          C                              2                                                                                                      )                                            ⁢                      s                                        +                    1                                                                                                                          =                            ⁢                                                                    1                    /                                          (                                                                        R                          1                                                ⁢                                                  C                          1                                                ⁢                                                  R                          2                                                ⁢                                                  C                          2                                                                    )                                                                                                  s                      2                                        +                                                                  (                                                                              1                                                                                          R                                1                                                            ⁢                                                              C                                1                                                                                                              +                                                      1                                                                                          R                                2                                                            ⁢                                                              C                                2                                                                                                                                    )                                            ⁢                      s                                        +                                          1                                                                        R                          1                                                ⁢                                                  C                          1                                                ⁢                                                  R                          2                                                ⁢                                                  C                          2                                                                                                                    .                                                                        (        3        )            However, the exact transfer function of this two-section RC is
                                                                                          T                  12                                ⁡                                  (                  s                  )                                            =                            ⁢                              1                                                                            R                      1                                        ⁢                                          C                      1                                        ⁢                                          R                      2                                        ⁢                                          C                      2                                        ⁢                                          s                      2                                                        +                                                            (                                                                                                    R                            1                                                    ⁢                                                      C                            1                                                                          +                                                                              R                            2                                                    ⁢                                                      C                            1                                                                          +                                                                              R                            2                                                    ⁢                                                      C                            2                                                                                              )                                        ⁢                    s                                    +                  1                                                                                                        =                            ⁢                                                1                  /                                      (                                                                  R                        1                                            ⁢                                              C                        1                                            ⁢                                              R                        2                                            ⁢                                              C                        2                                                              )                                                                                        s                    2                                    +                                                            (                                                                        1                                                                                    R                              1                                                        ⁢                                                          C                              1                                                                                                      +                                                  1                                                                                    R                              2                                                        ⁢                                                          C                              2                                                                                                      +                                                  1                                                                                    R                              1                                                        ⁢                                                          C                              2                                                                                                                          )                                        ⁢                    s                                    +                                      1                                                                  R                        1                                            ⁢                                              C                        1                                            ⁢                                              R                        2                                            ⁢                                              C                        2                                                                                                                                                    (        4        )            It is obvious to see the difference of equation (4) from equation (3).
Notice that the disclosed recursive algorithm requires a recursive algorithm involving two steps back data. This method and algorithm exactly recover the exact transfer function in a so effective way in both systematic elegance and calculation complexity. Thus, this fact implies that all one step back recursive algorithms are either not correct for an exact transfer function derivation if no load effect adjustment, or not efficient in computation complexity for derivation of the exact transfer function.
In all, current conventional methods are lack of an elegant way to get exact original high order state space model and effective recursive transfer function of distributed interconnect and transmission line.